\documentclass[11pt,twoside,a4paper]{article}

\usepackage[french]{babel}
%\usepackage{a4}
\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
%\usepackage{algorithmic}
%\usepackage{algorithm}

% Style bibliographique
\bibliographystyle{plain}
%--- Definitions de nouvelles commandes ---
\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\R}{\mathbb{R}} % les rationnels
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\K}{\mathbb{K}} % un corps
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\M}{\mathcal{M}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OK}{\mathcal{O}_K}
\newcommand{\courbe}{\mathcal{C}} % une courbe avec un joli C
\newcommand{\jac}{\operatorname{Jac}(\mathcal{C})} %la jacobienne
\newcommand{\jacone}{\operatorname{Jac}(\mathcal{C}_1)} %la jacobienne
\newcommand{\jactwo}{\operatorname{Jac}(\mathcal{C}_2)} %la jacobienne
\newcommand{\Nm}{\mathcal{N}_{\K/\Q}}
\newcommand{\ag}{\mathfrak{a}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{heuristic}{Heuristic}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
%\renewcommand{\algorithmicrequire}{\textbf{Input:}}
%\renewcommand{\algorithmicensure}{\textbf{Output:}}

%\newcommand{\algorithmicreturn}{\textbf{return}}
%--- Pour le titre ---
\title{Programme de recherche}
\author{Jean-Fran\c{c}ois Biasse \\
biasse@lix.polytechnique.fr}
\date{}
%============================= Corps =================================
\begin{document}
\maketitle            % écrit le titre
%\tableofcontents      % écrit la table des matières



\section{Introduction}

Mon programme de recherche pour les années à venir concerne le développement d'algorithmes efficaces pour résoudre 
des problèmes de théorie des nombres et de calcul formel, ainsi que l'étude de leurs applications à la cryptologie. 
Depuis la fin des année 1970 et l'avènement des cryptosystèmes à clef publique~\cite{DH, RSA}, une grande partie de 
la recherche en calcul formel se focalise sur les problématiques ayant trait à la sécurité informatique. La sécurité 
des échanges et du stockage de données repose sur 
la difficulté présumée de certains problèmes mathématiques. Ainsi, le problème dit du \og logarithme discret \fg est 
à la base de l'authentification et de l'échange de clef sur les réseaux numériques tels que l'internet, tandis que la 
difficulté de factoriser des entiers de grande taille protège les échanges dans le cadres des protocoles dits 
\og à clef publique \fg. L'efficacité de ces primitives cryptographique repose sur la réalisation de nombreuses 
opérations arithmétiques dans des structures algébriques, et revêt un caractère crucial dans les contextes où les 
ressources sont limitées, comme c'est le cas pour les systèmes embarqués.

L'étude d'algorithmes de résolution de problèmes sur lesquels peuvent reposer des cryptosystèmes intersecte bien 
souvent les préoccupations parfois anciennes des théoriciens des nombres, tout en fournissant des défis aux chercheurs 
en calcul formel. Par exemple, la célèbre hypothèse de Riemann qui est une conjecture non prouvée remontant au milieu 
du XIXième siècle permet de décrire la distribution des nombres premiers, contribuant ainsi à l'analyse de la complexité 
du crible algébrique, meilleur algorithme de factorization de grands entiers connus à ce jour. Parmi les problèmes de 
théorie des nombres utilisés en cryptologie, le logarithme discret dans la jacobienne d'une courbe algébrique apparaît 
comme l'un des plus prometteurs pour les cryptosystèmes des années à venir. En effet, il permet l'emploi de clefs de 
taille plus petites que RSA, son concurent direct, pour une sécurité équivalente. De plus, les meilleures attaques 
contre le problème du logarithme discret dans la jacobienne d'une courbe algébrique sont de complexité exponentielle 
dans les classes de courbes de genre fixé tandis que le crible algébrique permet la factorisation d'entiers en complexité 
heuristique sous-exponentielle $L(1/3,O(1))$.

Je compte m'intéresser à des sujets différents ayant pour point commun des applications à la cryptographie et à la 
théorie des codes. Pour cela, je m'appuierai sur les résultats que 
j'ai obtenus durant ma thèse dans le domaine de la théorie algorithmique des nombres, ainsi que ceux obtenus en calcul 
formel durant mes recherches postdoctorales. Les axes principaux que je souhaite développer sont la résolution du logarithme 
discret dans les corps de fonctions, l'étude de la mise en forme canonique de bases de modules, et la multiplication 
complexe, qui est actuellement un sujet de préoccupations important dans la communauté cryptologique.


%Ces résultats ont des applications directes 
%dans le calcul d'isogénies entre courbes elliptiques. Les techniques de cribles que j'ai employées pour le calcul du 
%groupe de classes d'ídéaux permettent de résoudre le problème du logarithme discret dans la jacobienne d'une courbe 
%algébrique. J'envisage aussi, à plus long terme, l'étude de l'optimisation des opérations arithmétiques élémentaires 
%dans les corps finis, ainsi que l'amélioration des algorithmes d'algèbre linéaire tels que le calcul de la forme normale 
%de Hermite d'une matrice.

%L'équipe-projet ARITH du département d'informatique du LIRMM est l'environnement de recherche idéal pour la réalisation d'un tel projet. Ses membres, que j'ai eu l'occasion de rencontrer lors d'une visite durant ma thèse, sont spécialisés dans les algorithmes efficaces de réalisation d'opérations arithmétiques, dans les algorithmes d'algèbre linéaire, ainsi que leurs applications à la cryptologie. De plus, le LIRMM héberge le groupe de recherche transdisciplinaire de \og cryptographie et sécurité numérique \fg dont le directeur Laurent Imbert fait partie de l'équipe ARITH. 

\section{Logarithme discret dans les corps de fonctions}\label{sec:log_disc}

Un courbe algébrique plane $\courbe$ sur un corps fini $\F_q$ est le lieu d'annulation d'un polynôme bivarié 
donné par 
$$P_{\courbe}(X,Y) = 0,$$
où $P_{\courbe}\in\F_q[X,Y]$. Pour une courbe hyperelliptique, le degré en $Y$ est 2. Dans ce cas, 
le genre, qui est un invariant de $\courbe$ définit par le degré en $X$ permet de les classifier. À une  
courbe sur un corps fini, on peut associer un groupe fini $\jac$ de manière analogue à la construction du
groupe de classes d'idéaux d'un corps de nombres. Ici, $\F_q(X)$ joue le rôle de $\Q$, et le corps de 
fonctions $\F_q(X)[Y]/(P_{\courbe})$ est l'analogue d'un corps de nombre $K/\Q$. La Jacobienne de $\courbe$ 
est alors définie par 
$$\jac := \{ \text{diviseurs de degré 0 de } \courbe\}/\{\text{diviseurs principaux}\}.$$ 
La Jacobienne de $\courbe$ est un groupe fini, et le borne de Hasse indique que 
$$\#\jac\approx \#\F_q^g = q^g.$$
La difficulté du problème du logarithme discret dans $\jac$ est à la base de nombreux cryptosystèmes. 
En particulier, le cas des courbes elliptiques ($g=1$) a attiré l'attention de la communauté cryptologique 
par la simplicité des opérations arithmétiques, et l'efficacité des implantations. Il y a cependant un 
intérêt croissant pour une meilleure compréhension des courbes hyperelliptique de genre $g\geq 2$, et pour 
les corps de fonctions de degré plus important d'une manière générale, en particulier dans l'éventualité 
de la découverte de nouvelles attaques ciblant des classes précises de courbes.

\paragraph{Crible quadratique}

%Les courbes elliptiques ne sont pas les seules dans lesquelles le problème du logarithme discret est intéressant, tant au niveau théorique que dans l'optique d'applications à la cryptographie. Les courbes hyperelliptiques de genre $g\geq 1$ sont une généralisation des courbes elliptiques, qui correspondent au cas $g=1$. La jacobienne  $\jac$ d'une courbe hyperelliptique de genre $g$ définie sur un corps fini $\F_q$ vérifie
%$$\#\jac\approx \#\F_q^g.$$
%Par conséquent, la difficulté du calcul de la structure de $\jac$ ainsi que de la résolution du problème du logarithme discret dans $\jac$ dépend à la fois de $q$ et de $g$. Les classes de courbes qui sont considérées commes les plus sûres sont celles de faible genre définies sur des corps finis de grande taille.
Les meilleurs algorithmes actuels pour la résolution du problème du logarithme discret dans les courbes hyperelliptiques sont basés 
sur la stratégie de la marche aléatoire. Cependant, Flassenberg et Paulus on introduit dans~\cite{FlaPau} un algorithme pour 
résoudre ce problème basé sur le crible quadratique. Cet algorithme utilise les mêmes méthodes de génération de relations que 
celle introduite par Jacobson~\cite{pell} dans le contexte des corps de nombres, et que j'ai utilisées et améliorées 
dans~\cite{biasse_quad,BiaJac10,BiaJacSil10}. Il s'agit de traiter l'anneau des coordonées
$\F_q[X][Y]/(P_{\courbe})$ comme un ordre dans un corps de nombres quadratique. Les relations dans $\jac$ sont obtenues par la 
recherche de valeurs friables de formes quadratiques 
$$\phi(U) = a(X)U^2 + b(X)U + c(X)\in \F_p[X][U].$$
Cette recherche s'effectue avec une version de l'algorithme du \textit{crible quadratique}~\cite{pomerance_quad_sieve}. 
Les seules implantations existantes de cet algorithme dans le cas des corps de fonctions ne sont 
efficaces que dans le cas des courbes de grand genre~\cite{velichka}. La plupart des améliorations 
des méthodes basées sur le crible quadratique que j'ai développées pour les corps quadratiques devraient avoir un impact 
comparable dans le cas des corps de fonctions, et en particulier dans les jacobiennes de courbes hyperelliptiques. 
Elles devraient notamment contribuer à baisser le genre minimal pour lequel le crible devient plus efficace que la marche 
aléatoire.

\paragraph{Applications à la cryptologie}
L'amélioration des performances pour les courbes de grand genre est intéressante du point de vue de la 
théorie des nombres, et elle peut aussi avoir des applications cryptographiques par des chemins détournés. En effet, 
il est possible de transporter le problème du logarithme discret de la jacobienne d'une courbe elliptique vers celle 
d'une courbe hyperelliptique de plus grand genre via la \og descente de Weil\fg. Naturellement, les courbes elliptiques 
sujettes à ce type d'attaques ont été bannies de tout usage cryptographique, mais cette faiblesse a été exploitée par 
Teske~\cite{teske} pour décrire d'un point de vue théorique un cryptosystème dans lequel l'utilisateur doit résoudre 
des instances du problème du logarithme discret dans la jacobienne d'une courbe de genre élevé. Les tailles mises en 
jeu ont pour l'instant empêché toute réalisation pratique d'un tel cryptosystème, mais l'amélioration de la recherche 
des relations via les méthodes de crible dans les courbes de grand genre pourrait lever cette obstruction.

\paragraph{Crible algébrique}

L'analogie entre les corps de fonctions de degré 2 et les corps quadratiques permet l'adaptation 
des techniques basées sur le crible quadratique pour le calcul de relations, et donc la résolution 
du problème du logarithme discret. Il est naturel de s'interroger sur ce qu'il en est des corps de 
fonctions de degré supérieur. En effet, j'ai récemment décrit, en collaboration avec Fieker, un 
algorithme analogue au crible algébrique~\cite{NFS} pour le calcul de relations dans le groupe de 
classes d'idéaux de corps de nombres de degré arbitraire. Cet algorithme, qui sera présenté 
dans~\cite{biasse_NFS}, a été implanté dans le logiciel de calcul formel Magma~\cite{magma}, et 
s'est révélé très efficace pour les corps de nombres de petit degré. La recherche de relations dans 
le groupe de classes d'un corps de fonction de degré $n$ peut se faire par le calcul de valeurs friables 
de polynômes de la forme 
$$\phi(U,V) = a_n(X)U^n + a_{n-1}(X)U^{n-1}V + \cdots + a_1(X)V^n\in F_q[X][U,V].$$
Il est permis d'espérer 
qu'une adaptation de ces techniques de crible pour la recherche de valeurs friables dans les corps de
fonctions permettrait d'atteindre des résultats comparables lorsque le degré en $Y$ de $\courbe$ est 
faible.  
%À l'instar du projet sur le calcul d'isogénies, cet axe de recherche s'inscrit dans le cadre du travail de Laurent Imbert, membre de l'équipe ARITH. Il est une généralisation plus ambitieuse de mes résultats pratiques découlant de mes travaux de thèse, mais devrait porter ses fruits sur le moyen terme.

%\section{Arithmétique efficace dans les corps finis}

%Les techniques de cribles impliquent la répétition de nombreuses opérations arithmétiques élémentaires dans le corps fini sur lequel est défini la courbe sur laquelle on cherche à résoudre le problème du logarithme discret. Ces opérations élémentaires commencent à être disponibles sur certains processeurs, mais cette situation est loin d'être une généralité. De fait, le choix d'un représentant optimisé pour le corps fini étudié, ainsi que l'optimisation pour cette représentation particulière des opérations arithmétiques élémentaires est d'un intérêt crucial pour la résolution du logarithme discret.

%Cet axe de recherche est plus éloigné de mon sujet de thèse, mais c'est une continuation logique de mes travaux dans la mesure où les améliorations en terme d'arithmétique dans les corps de nombres auront un impact immédiat dans la résolution du logarithme discret. De plus, le domaine de l'arithmétique optimisée est l'un des sujets phares de l'équipe ARITH qui compte des spécialistes du domaine tels que Laurent Imbert et Pascal Giorgi, et qui s'est développé considérablemement grâce aux contributions de Jean-Claude Bajard, ancien membre aujourd'hui en poste à Paris 6.	

\section{Algorithmes efficaces de mise sous forme canonique}

Étant donné un anneau $R$, et un $R$-module $M$ de dimension $n$, une tâche essentielle en calcul formel est le calcul de 
$b_1,\cdots,b_n$ jouissant de bonnes propriétés et telle que 
$$M = R b_1 + \cdots + R b_n.$$
Par exemple, dans le cas $R = \Z$, l'algorithme LLL~\cite{LLL} permet de trouver une base de $M$ ayant de courts 
vecteurs, facilitant ainsi la résolution de la recherche du plus court vecteur dans $M$, ou bien la recherche 
du vecteur le plus proche dans $M$. Cet algorithme a de nombreuses applications en cryptographie des 
réseaux. Un autre exemple typique est la mise sous forme de Hermite (HNF) d'un 
système de générateurs du $\Z$-module $M$ des relations d'un groupe abélien $G$. Soient $(g_1,\cdots,g_n)$ des 
générateurs de $G$, à chaque relation de la forme 
$$g_1^{e_1}\cdots g_n^{e_n} = 1,$$
correspond un vecteur $(e_1,\cdots,e_n)\in M$. Le calcul d'une base en forme HNF de $M$ consiste en 
l'application d'opérations unimodulaire à la matrice représentant les générateurs de $M$ afin 
de la mettre sous forme triangulaire. Cela permet notamment 
le calcul de la structure de $G$, et la résolution du problème du logarithme discret dans $G$. Dans le 
cas où $G = \jac$, les algorithme de mise sous forme canonique ont un impact direct sur les axes de 
recherche développés au \S~\ref{sec:log_disc}.

\paragraph{Forme de Hermite}

Les implantations actuelles du calcul de la forme HNF d'une matrice à coefficients dans $\Z$  
prennent peu ou pas en compte les spécificité liés aux applications à la théorie des nombres et à la 
cryptologie. En effet, des résultats récents sont venus améliorer la complexité 
du calcul de la HNF dans le cas général~\cite{PerStein11,Sto_quasi_opt}, mais le cas spécifique 
des matrices traitées pendant les algorithmes de calcul d'index a été traité pour la dernière fois
dans~\cite{JacobsonHNF}. J'ai réalisé une implantation basées sur les idées de~\cite{JacobsonHNF} dans 
la bibliothèque C++ linbox\cite{linbox} en collaboration avec les membres de l'équipe CASYS au laboratoire 
Jean Kunzmann de Grenoble. Cependant, cet angle de recherche mérite d'être approfondi, en mettant notamment
l'accent sur les améliorations pratiques heuristiques. 


En ce qui concerne la complexité théorique, de nombreux problèmes d'algèbre linéraire sur les matrices polynomiales 
carrées peuvent être 
désormais résolus par des algorithmes en complexité $\tilde{O}(n^{\omega}d)$, où $\tilde{O}$ dénote la 
complexité amortie (c'est à dire sans les facteurs logarithmiques), $n$ la dimension de la matrice et 
$d$ une borne sur le degré des entrées. Citons par exemple la résolution de systèmes linéaires par 
lift $p$-adique, le calcul de déterminant, le calcul de forme normale de 
Smith~\cite{Sto02_lift,Sto03_lift}, la réduction rapide de ligne de~\cite{Giorgi_pol_mat}, ainsi que 
le calcul d'une base approximante minimale~\cite{Giorgi_pol_mat,arne}. Il est aussi notable que 
le calcul explicite de l'inverse d'une matrice, dont la taille est en $\Omega(n^3 d)$, peut être réalisé 
en temps quasi-optimal $\tilde{O}(n^3d)$ (voir~\cite{villard_inv_pol_mat,Sto_inv_mat}). 
Récemment~\cite{Sto_quasi_opt}, Storjohann et Gupta ont montré que la HNF d'une matrice polynomiale 
pouvait être calculée en temps $(n^3d)^{1+o(1)}$. Ainsi que mentionné dans~\cite{Sto_quasi_opt}, malgrès 
l'espoir suscité par l'existence d'algorithmes optimaux pour les problèmes d'algèbre linéaire connexes, 
l'élaboration d'un algorithme en $\tilde{O}(n^{\omega}d)$ pour le calcul de la HNF nécessitera de 
nouvelles idées. Je souhaite étudier les méthodes permettant le rapprochement des performances des 
algorithmes de mise en forme HNF vers le temps optimal. 


\paragraph{Pseudo-base d'un $\OK$-module}

Un $\OK$-module $M\subseteq K^l$, où $K$ est un corps de nombres et $\OK$ son 
anneau des entiers, peut être décrit par une \textit{pseudo-base}, c'est à dire des idéaux fractionnaires 
$(\ag_i)_{i\leq n}$ et des éléments $(A_i)_{i\leq n}$ de $K^l$ tels que 
$$M = \ag_1 A_1 \oplus \cdots \oplus \ag_n A_n.$$
Indépendamment des propriétés de $M$, la taille des $\ag_i$ et des $A_i$ peut être arbitrairement grande.
La construction d'une bonne base pour un $\OK$-module  a reçu dernièrement une attention considérable de la part de la communauté 
scientifique. En effet, les $\OK$-modules interviennent en cryptographie basée sur les 
réseaux~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, où la sécurité des 
cryptosystèmes repose sur la difficulté de trouver le vecteur le plus court, ou le vecteur le plus proche. 
La forme normale de Hermite pour les $\OK$-modules, décrite par 
Cohen~\cite[Chap. 1]{cohen2} intervient dans les calculs de base réduite, notamment au travers 
de l'algorithme de Fieker et Stehl{\'e}~\cite{stehle_fieker_LLL}, et a par conséquent 
des applications en cryptographie et en théorie des codes. J'ai récemment décrit~\cite{pseudo_HNF}, 
en collaboration avec Fieker. le premier algorithme en complexité polynomiale pour le calcul de HNF 
pour un $\OK$-module. Il est essentiellement l'équivalent de l'algorithme de Kannan-Bachem~\cite{KannBach}, 
décrit il y a plus de 30 ans. Il est raisonnable d'espérer généraliser dans un premier temps 
les stratégies les plus efficaces connues pour les entiers, notamment 
l'algorithme de Micciancio~\cite{MicWar01}, celui de Storjohann et al.~\cite{JacobsonHNF} et 
l'approche modulaire de Pernet et Stein~\cite{PerStein11}. Dans un deuxième temps, il sera intéressant 
de s'interroger sur la possibilité de se rapprocher des performances optimales, à l'instar de la 
HNF classique.


\paragraph{Aspects parallèles}

L'augmentation de la puissance de calcul des machines se fait désormais plus par l'ajout de nouveaux 
coeurs plutôt que par l'augmentation de la cadence des processeurs. La parallélisation des algorithmes 
est donc un défi majeur dans le cadre des implémentations efficaces pour le futur. De plus, dans 
certains algorithmes tels que le calcul de la structure de groupe ou de logarithmes discrets, 
la création de la matrices des relations est trivialement parallélisable tandis que sa mise en forme canonique de Hermite ou de Smith, 
suivant l'usage qui est fait, est beaucoup moins évidente. Ainsi, les calculs d'algèbre linéraire en 
général sont l'obstruction majeure à une parallélisation efficace des algorithmes de calculs d'index 
pour la théorie algorithmique des nombres et la cryptologie.

Toutefois, des études ont été menées dans le but de paralléliser la mise en forme de Hermite et de 
Smith d'une matrice. Ainsi, des versions parallèles de la SNF et de la HNF pour les matrices à 
coefficients polynomiaux ont été décrites notamment 
dans~\cite{Kaltofen_SNF_par, Wagner_SNF_par}. Elles reposent sur la possibilité de calculer le PGCD 
de polynômes en parallèle. Aussi, dans le cadre des matrices dans $\Z$, le calcul du déterminant d'une 
matrice carrée peut se faire modulo plusieurs nombres premiers en parallèle avant d'être reconstruit par 
restes chinois. Cette méthode a été utilisée notamment dans le cadre du calcul d'index~\cite{JacobsonPhd} 
afin d'accélérer les calculs de HNF et de SNF. 

Une des directions vers lesquelles je compte m'orienter pour améliorer l'état de l'art est 
celle des stratégies récursives par blocs. Pour cela, il faut notamment disposer de méthodes parallèles 
pour la multiplication des blocs, et d'une sychronisation efficace des processus. La multiplication parallèle 
de matrices génère actuellement beaucoup d'intérêt, et les algorithmes actuels ne permettent pas encore de diviser 
le temps par le nombre 
de coeurs disponibles. Cet état de fait a notamment été mis en évidence à la conférence PASCO 2010 durant 
laquelle une compétition entre les différentes implantations de multiplication parallèle de matrices sur 
les entiers s'est tenue. Beaucoup de moyens sont actuellement mis en oeuvre pour combler ce manque car 
c'est un domaine porteur pour les années à venir.  



%\paragraph{Forme de Hermite ad-hoc dans $\Z$}
%
%Les implantations actuelles de la mise sous forme HNF d'une matrice à coefficients dans $\Z$  
%prennent peu ou pas en compte les spécificité liés aux applications à la théorie des nombres et à la 
%cryptologie. C'est pourtant un chantier considérable, en comparaison de l'attention reçue par les 
%matrices aléatoires. En effet, de nombreux résultats théoriques sont venus améliorer la complexité 
%du calcul de la HNF dans le cas général[?], mais l'état de l'art dans le cas spécifique des matrices 
%traitées pendant les algorithmes de calcul d'index a été traité pour la dernière fois
%dans~\cite{JacobsonHNF}. J'ai réalisé une implantation basées sur les idées de~\cite{JacobsonHNF} dans 
%la bibliothèque C++ linbox\cite{linbox} en collaboration avec les membres de l'équipe CASYS au laboratoire 
%Jean Kunzmann de Grenoble, mais cet angle de recherche recèle de possibilités qui peuvent se traduire 
%par des écarts de temps de calcul considérable. Cette absence d'algorithme dédié nuit certainement aux 
%performances des algorithmes de théorie des nombres disponibles à ce jour. La cause en est certainement 
%le manque de personnes travaillant à la fois en théorie algorithmique des nombres et en calcul formel, 
%manque que j'espère contribuer à combler via le présent projet de recherche.

%\paragraph{Forme de Hermite en temps optimal}

%De nombreux problèmes d'algèbre linéraires sur les matrices polynomiales carrées peuvent être 
%désormais résolus par des algorithmes en complexité $\tilde{O}(n^{\omega}d)$, où $\tilde{O}$ dénote la 
%complexité amortie (c'est à dire sans les facteurs logarithmiques), $n$ la dimension de la matrice et 
%$d$ une borne sur les degrés des entrées. Citons par exemple la résolution de systèmes linéaires par 
%lift $p$-adique, le calcul de déterminant, le calcul de forme normale de 
%Smith~\cite{Sto02_lift,Sto03_lift}, la réduction rapide de ligne de~\cite{Giorgi_pol_mat}, ainsi que 
%le calcul d'une base approximante minimale~\cite{Giorgi_pol_mat,arne}. Il est aussi notable que 
%le calcul explicite de l'inverse d'une matrice, dont la taille est en $\Omega(n^3 d)$ peut être réalisé 
%en temps quasi-optimal $\tilde{O}(n^3d)$ (voir~\cite{villard_inv_pol_mat,Sto_inv_mat}). 
%Récemment~\cite{Sto_quasi_opt}, Storjohann a montré que la HNF d'une matrice polynomiale pouvait 
%être calculée en temps $(n^3d)^{1+o(1)}$. Il y a donc une marge de progression 
%concernant le temps de calcul de la HNF sur les matrices polynomiale. Cette remarque est 
%\textit{a fortiori} valable pour les matrices à coefficients dans $\Z$ pour lesquelles il n'existe 
%encore pas d'algorithme en temps quasi-optimal équivalent à celui présenté 
%dans~\cite{Sto_quasi_opt}. Combler le retard pris par les algorithmes de calcul de HNF sur $\Z$ 
%est une première étape. Après celà, je souhaite oeuvrer au rapprochement des performances des 
%algorithmes de mise en forme HNF vers le temps optimal. 

%\paragraph{Forme de Hermite pour les $\OK$-modules}

%La construction d'une bonne base pour un $\OK$-module où $K$ est un corps de nombres et $\OK$ son 
%anneau des entiers a reçu dernièrement un attention considérable de la part de la communauté 
%scientifique. En effet, les $\OK$-modules interviennent en cryptographie basée sur les 
%réseaux~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, où la sécurité des 
%cryptosystèmes repose sur la difficulté de trouver le vecteur le plus court, ou le vecteur le plus proche. 
%La forme normale de Hermite pour les $\OK$-modules, décrite par 
%Cohen~\cite[Chap. 1]{cohen2} intervient dans les calculs de base réduite, et a par conséquent 
%des applications en cryptographie et en théorie des codes. J'ai récemment décrit~\cite{pseudo_HNF} 
%le premier algorithme en complexité polynomiale pour le calcul de HNF pour un $\OK$-module. Il 
%est essentiellement l'équivalent de l'algorithme de Kannan-Bachem~\cite{KannBach}, décrit il y a plus 
%de 30 ans. Il existe donc un retard considérable entre les progrès réalisés pour la forme normale 
%sur $\Z$ (et \textit{a fortiori} pour les polynômes dans les corps finis) et l'état de l'art actuel des algorithmes 
%pour le calcul de la généralisation de la HNF pour les modules sur les anneaux de Dedekind. Ainsi, 
%il est raisonnable d'espérer généraliser les algorithmes les stratégies les plus efficaces connues 
%pour les entiers, notamment l'algorithme de Micciancio~\cite{MicWar01}, celui de 
%Storjohann et al.~\cite{JacobsonHNF} et l'approche modulaire de Pernet et Stein~\cite{PerStein11}. 
%À l'instar du cas des entiers, les performances de la HNF sur les 
%$\OK$-modules doivent pouvoir être rapprochées de celles de la HNF sur les polynômes, et doivent 
%pouvoir, dans le futur, tendre vers les performances optimales.  


\section{Multiplication complexe}

La théorie de la multiplication complexe est un trait d'union entre les résultats obtenus durant 
ma thèse en théorie algorithmique des nombres et l'étude des courbes algébriques. Plus 
particulièrement, la théorie de la multiplication complexe identifie l'anneau d'endomorphismes 
de $\jac$, pour certaines $\courbe$ dites dotées de la multiplication complexe (courbe CM), à un 
ordre dans un corps de nombres
$$\operatorname{End}(\jac)\simeq \OO.$$
De plus, étant données deux courbes munie de multiplication complexe $\courbe_1$ et $\courbe_2$ 
sur un corps fini , la théorie de la multiplication complexe permet la construction explicite 
d'isogénies $$\varphi : \courbe_1\longrightarrow\courbe_2,$$
lorsque elles existent, induisant un morphisme $\jactwo\rightarrow\jacone$. En particulier, le problème du logarithme 
discret dans $\jactwo$ se réduit réduit au même problème sur $\jacone$. C'est une des raisons 
pour lesquelles le calcul d'isogénies est le sujet d'études intenses de la part de la communauté 
cryptographique. Une isogénie est une application rationnelle, et plus son degré est élevé, 
plus il est difficile de la calculer. Le calcul d'isogénies de large degré est donc un défi 
important. L'étude de $\operatorname{End}(\jac)$ est aussi important dans la construction de 
courbes ad-hoc pour un usage cryptographique. Elle permet notamment de contrôler le nombre de 
points des courbes facilement, et \textit{in fine} la construction de courbes adaptées aux 
couplages qui sont appliqués dans le context de la cryptographie basée sur l'identité \og 
identity based encryption \fg. 


\paragraph{Courbe elliptiques}

Le cas des courbes elliptiques est le plus facile à traiter car on peut se ramener à des 
calculs dans un ordre quadratique pour lequel l'utilisation de représentations à l'aide 
de formes quadratiques permet des calculs optimisés. Ainsi, étant donnée une courbe 
elliptique $E$ sur un corps fini, son anneau d'endomorphismes satisfait 
$$\operatorname{End}(\jac)\simeq \OO$$
pour un certain ordre $\Z[\pi]\subseteq\OO\subseteq\OK$ où $\pi$ est le Frobenius et $\OK$ l'ordre 
maximal de $K:= \Q(\sqrt{\pi})$. Bisson et Sutherland~\cite{BisSut09} ont montré comment
calculer $\OO$ à partir de relations dans $\Cl(\OO')$ pour $\Z[\pi]\subseteq \OO'\subseteq \OK$. 
Les méthodes qu'ils ont utilisées sont beaucoup plus lentes que celles basées sur le crible 
quadratique que j'ai employées dans~\cite{biasse_quad,BiaJac10,BiaJacSil10}. De même, le 
calcul explicite d'isogénies de large degré entre deux courbes elliptiques de même anneau 
d'endomorphisme se fait par identification 
$$\left(\varphi:E_1\rightarrow E_2\right) \longleftrightarrow \ag_{\varphi}\in \Cl(\OO),$$ 
où $\OO \simeq \operatorname{End}(E_i)$. Une isogénie de large degré correspond à la classe 
d'un idéal de large norme dans $\Cl(\OO)$. Br{\"o}ker, Charles et Lauter~\cite{BCL} ont 
décrit comment décomposer cet idéal comme produit d'idéaux de plus faible norme afin de 
réduire la difficulité du calcul, mais à l'instar de Bisson et Sutherland~\cite{BisSut09}, 
ils n'ont pas fait usage des méthodes basées sur le crible quadratique~\cite{biasse_quad,BiaJac10,BiaJacSil10} 
qui, selon toute vraisemblance, devraient permettre de réaliser des améliorations 
considérables. Ainsi, malgrès le fait que le genre 1 ait été étudié en profondeur ces 
dernière années, je pense que les méthodes dédiées pour les corps quadratiques apporteront 
des améliorations pratiques qui feront une grande différence dans les implantations.

\paragraph{Genre $g\geq 2$}

La théorie de la multiplication complexe peut être appliquée aux variétés abéliennes 
en général, et plus particulièrement aux courbes hyperelliptiques de genre $g\geq 2$ 
(c'est à dire non elliptiques). Dans ce cas, si l'algèbre 
$$\Q\otimes\jac$$
contient un corps de nombres $K$ de degré $2g$, on dit que $\jac$ admet une 
\textit{multiplication complexe} par le corps $K$. Les cas des courbes elliptiques 
est aujourd'hui très bien balisé, mais il n'en est pas de même pour le genre 2, et 
\textit{a fortiori} pour $g > 2$. La principale raison est que la théorie est 
beaucoup plus compliquée, mais c'est aussi dû au fait que l'état de l'art ne permet 
pas encore de rejoindre les performances du cas elliptique en terme d'efficacité des 
implantations. Aujourd'hui, le genre 2 préoccupe 
de nombreux chercheurs dans le domaine car outre le désir de compléter l'étude de 
l'anneau d'endomorphisme et des isogénies entre courbes à multiplication complexe, 
il existe aussi un espoir de réaliser des opérations arithmétiques de manière plus 
efficaces dans la Jacobienne d'une courbe de genre $g\geq 2$. 

Les difficultés techniques sont considérables, notamment à cause du calcul 
des polynômes modulaires, donnée essentielle pour calculer les isogénies 
entre courbes de manière directe (sans passer par une décomposition telle que décrite 
dans~\cite{BCL}). Ainsi, les calculs dans $\Cl(\OO)$, où $\OO\subseteq \OK$ sont plus 
difficiles car il faut faire apparaître des relations impliquant des idéaux de faible 
norme, ce qui est une contrainte importante. Une piste pour les rendre plus efficace 
est l'utilisation de méthodes dédiées pour les corps de faibles degrés, à l'image de 
ce qui est faisable dans les 
corps quadratiques. J'ai décrit un algorithme de crible algébrique pour le calcul 
de relations dans $\Cl(\OO)$ qui s'est révélé très efficace lorsque la dimension de 
$K$ est petite (typiquement $n\leq 7$). Une adaptation de cette méthode dans le cadre 
du calcul de l'anneau d'endomorphismes et d'isogénies est susceptible de porter ses fruits pour les 
genre $g=2,3$ (c'est à dire correspondant à des corps de degré 4 ou 6). Une méthode 
alternative est la description d'algorithmes dédiés pour l'arithmétique dans les corps de petit 
degré, à l'image de ce qui a été fait 
pour les corps quadratiques avec l'usage de l'arithmétique sur les formes quadratiques. 
Enfin, une troisième voie consiste en la recherche de meilleurs invariants pour les 
calculs de polynômes modulaires. Par exemple, pour les courbes elliptiques, deux courbes 
$E_1$ et $E_2$ sont reliées par une isogénie de degré $l$ si 
$$\Phi_l(j(E_1),j(E_2))=0,$$
où $j(E)$ dénote le $j$-invariant de $E$ et $\Phi_l$ le $l$-ième polynôme modulaire. 
Br\"{o}ker, Lauter et Sutherland ont montré dans~\cite{drew_mod_pol} que l'usage 
de polynomes modulaires pour d'autres invariants pouvait réduire les temps de calcul 
de manière significative. Une telle stratégie se généralise certainment au cas $g\geq 2$, 
permettant ainsi de surmonter en partie les difficultés liées aux genres supérieurs.




\section{Conclusion}

Mon programme de recherche, motivé par les aspects de théorie des nombres de la cryptologie, 
couvre divers sujets relevant du calcul formel. C'est un programme en lien avec mes travaux 
antérieurs, comportant des axes de recherche à court, moyen et long terme.  
%J'ai mentionné explicitement l'équipe ARITH du 
%LIRMM, laboratoire dans lequel il peut s'incrire, mais ces thématiques sont aussi développées dans 
%d'autres équipe du CNRS telles que l'équipe de calcul formel et cryptographie de l'IRMAR à Rennes, 
%l'équipe-projet commune CNRS-INRIA CARAMEL à Nancy, l'équipe projet commune CNRS-INRIA ARENAIRE à Lyon, 
%sans oublier l'équipe de cryptographie de l'École Polytechnique au sein de laquelle j'ai eu le plaisir 
%d'effectuer ma thèse. 

\bibliography{programme}

\end{document}